区间型动态规划——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

一、石子合并

问题描述：

• 有 n 堆石子排成一排 stones[n]，每堆石子有一定的数量。每次只能合并相邻的两堆石子，合并的代价为两堆石子的总数。求将所有石子合并成一堆的最小总代价
• 提示：
  • 1 <= n <= 100
  • 1 <= 数量 <= 100
• 示例 1：
  • 输入：stones = [3, 4, 3]
  • 输出：17
  • 解释：(3+4)+(7+3)=7+10=17
• 示例 2：
  • 输入：stones = [4, 1, 1, 4]
  • 输出：18
  • 解释：(1+1)+(4+2)+(6+4)=2+6+10=18

算法解析：

1. 定义状态：dp[i][j] 表示合并第 i 堆到第 j 堆石子的最小总代价（1 <= i <= j <= n）。
2. 预处理前缀和：计算前缀和数组 sum，sum[i] 表示前 i 堆石子的总数，sum[j] - sum[i-1] 即为第 i 到 j 堆石子的总数（合并时的基础代价）。
3. 初始状态：当 i == j 时，dp[i][j] = 0（单堆石子无需合并，代价为 0）。
4. 状态转移：对于区间 [i, j]，枚举分割点 k（i <= k < j），将区间拆分为 [i, k] 和 [k+1, j]，则：
   • dp[i][j] = min(dp[i][k] + dp[k+1][j]) + (sum[j] - sum[i-1])
   • 解释：dp[i][k] + dp[k+1][j] 是合并左右两部分的代价，sum[j]-sum[i-1] 是将左右两部分合并成一堆的代价。
5. 遍历顺序：按区间长度从小到大遍历（先算短区间，再算长区间），因为长区间的解依赖于更短的子区间。
6. dp[1][n] 合并1到n堆的最小代价

#include <iostream>
#include <vector>
using namespace std;

int stoneMerge(vector<int>& stones) {
    int n = stones.size();
    if (n <= 1) return 0;

    // 1. 预处理前缀和（下标从1开始，方便计算）
    vector<int> sum(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i - 1] + stones[i - 1];
    }

    // 2. 初始化dp数组：dp[i][j]表示合并i到j堆的最小代价
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    // 3. 按区间长度遍历（len表示区间长度，从2到n）
    for (int len = 2; len <= n; ++len) {
        // i是区间起点，j = i + len - 1是区间终点
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX; // 初始化为极大值

            // 枚举分割点k
            for (int k = i; k < j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
            }
        }
    }

    // 合并1到n堆的最小代价
    return dp[1][n];
}

int main() {
    // 测试用例：石子堆 [3, 4, 3]，最小代价：(3+4)+(7+3)=7+10=17
    vector<int> stones1 = {3, 4, 3};
    cout << stoneMerge(stones1) << endl; // 输出 17

    // 测试用例：石子堆 [4, 1, 1, 4]，最小代价：(1+1)+(4+2)+(6+4)=2+6+10=18
    vector<int> stones2 = {4, 1, 1, 4};
    cout << stoneMerge(stones2) << endl; // 输出 18

    return 0;
} 
        

输出结果

17
18
        

二、戳气球（LeetCode 312）

问题描述：

• 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
  • 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
  • 求所能获得硬币的最大数量。
• 提示：
  • n == nums.length
  • 1 <= n <= 300
  • 0 <= nums[i] <= 100
• 示例 1：
  • 输入：nums = [3,1,5,8]
  • 输出：167
  • 解释：
    • nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
    • coins = 3 * 1 * 5 + 3 * 5 * 8 + 1*3*8 + 1*8*1 = 167
• 示例 2：
  • 输入：nums = [1,5]
  • 输出：10

算法解析：

1. 定义状态：dp[i][j] 表示戳破区间 (i, j) 内（不包含 i 和 j）所有气球能获得的最大硬币数。
2. 边界处理：为了避免边界判断，在 nums 数组首尾各添加一个 1（因为戳破边界气球时，相邻的虚拟气球值为 1）。
3. 状态转移：假设最后戳破的气球是 k（i < k < j），则 dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])。
4. 遍历顺序：按区间长度从小到大遍历（因为长区间依赖短区间的结果）。
5. dp[0][len - 1] 最终结果是戳破(0, len-1)区间内的所有气球

#include <iostream>
#include <vector>

using namespace std;

int maxCoins(vector<int>& nums) {
    // 步骤1：处理边界，首尾添加1，简化边界判断
    int n = nums.size();
    vector<int> new_nums(n + 2, 1); // 初始化所有元素为1
    for (int i = 0; i < n; ++i) {
        new_nums[i + 1] = nums[i];
    }
    int len = new_nums.size(); // 新数组长度为n+2

    // 步骤2：初始化dp数组，dp[i][j]表示戳破(i,j)区间内气球的最大硬币数
    vector<vector<int>> dp(len, vector<int>(len, 0));

    // 步骤3：按区间长度从小到大遍历（长度从2开始，因为长度1时区间内无气球）
    for (int length = 2; length < len; ++length) {
        // 遍历所有起始位置i
        for (int i = 0; i < len - length; ++i) {
            int j = i + length; // 区间结束位置j
            // 遍历区间内所有可能最后戳破的气球k
            for (int k = i + 1; k < j; ++k) {
                // 状态转移：最后戳破k，累加左右区间结果 + 戳k的硬币数
                int current = dp[i][k] + dp[k][j] + new_nums[i] * new_nums[k] * new_nums[j];
                dp[i][j] = max(dp[i][j], current);
            }
        }
    }

    // 最终结果是戳破(0, len-1)区间内的所有气球（即原始数组的所有气球）
    return dp[0][len - 1];
}

int main() {
    // 示例1：输入 [3,1,5,8]，输出 167
    vector<int> test1 = {3, 1, 5, 8};
    cout << "Test1 result: " << maxCoins(test1) << endl; // 输出167

    // 示例2：输入 [1,5]，输出 10
    vector<int> test2 = {1, 5};
    cout << "Test2 result: " << maxCoins(test2) << endl; // 输出10

    return 0;
}
        

输出结果

Test1 result: 167
Test2 result: 10
            

三、最长回文子序列（LeetCode 516）

问题描述：

• 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
  • 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
• 提示：
  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成
• 示例 1：
  • 输入：s = "bbbab"
  • 输出：4
  • 解释：一个可能的最长回文子序列为 "bbbb" 。
• 示例 2：
  • 输入：s = "cbbd"
  • 输出：2
  • 解释：一个可能的最长回文子序列为 "bb" 。

算法解析：

1. 定义状态：dp[i][j] 表示字符串 s 中从索引 i 到 j（闭区间）的子串的最长回文子序列长度。
2. 边界处理：
   • 当 i == j 时，dp[i][j] = 1（单个字符本身是长度为 1 的回文）；
   • 当 i > j 时，dp[i][j] = 0（空串的回文长度为 0）。
3. 状态转移：
   • 如果 s[i] == s[j]，则 dp[i][j] = dp[i+1][j-1] + 2（两端字符相同，加入后回文长度 + 2）；
   • 如果 s[i] != s[j]，则 dp[i][j] = max(dp[i+1][j], dp[i][j-1])（取去掉左端点或右端点后的最大值）。
4. 遍历顺序：按子串长度从小到大遍历（因为长区间依赖短区间的结果）。
5. dp[0][n-1] 最终结果是整个字符串的最长回文子序列长度

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int longestPalindromeSubseq(string s) {
    int n = s.size();
    // 步骤1：初始化dp数组，dp[i][j]表示s[i..j]的最长回文子序列长度
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // 步骤2：初始化边界条件（单个字符的回文长度为1）
    for (int i = 0; i < n; ++i) {
        dp[i][i] = 1;
    }
    
    // 步骤3：按子串长度从小到大遍历（长度从2到n）
    for (int len = 2; len <= n; ++len) {
        // 遍历所有起始位置i
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1; // 子串结束位置j
            // 情况1：两端字符相同
            if (s[i] == s[j]) {
                if (len == 2) {
                    dp[i][j] = 2; // 两个相同字符，长度直接为2
                } else {
                    dp[i][j] = dp[i+1][j-1] + 2;
                }
            } 
            // 情况2：两端字符不同
            else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    
    // 最终结果是整个字符串的最长回文子序列长度
    return dp[0][n-1];
}

int main() {
    // 示例1：输入 "bbbab"，输出 4（最长回文子序列是 "bbbb"）
    string test1 = "bbbab";
    cout << "Test1 result: " << longestPalindromeSubseq(test1) << endl; // 输出4

    // 示例2：输入 "cbbd"，输出 2（最长回文子序列是 "bb"）
    string test2 = "cbbd";
    cout << "Test2 result: " << longestPalindromeSubseq(test2) << endl; // 输出2

    return 0;
}
        

输出结果

Test1 result: 4
Test2 result: 2